The present invention relates generally to cell relay systems and, more particularly, to a cell relay switch with a merged buffer architecture.
Asynchronous transfer mode (ATM) switches provide high-speed data exchange while minimizing the impact on overall system bandwidth. ATMs are commonly used in local area networks (LANs) and wide area networks (WANs). Recently, however, ATM switches have been used in wideband data transfer protocols, such as synchronous optical network (SONET) and synchronous transport stream (STS) systems.
FIG. 1 is a block diagram of a conventional ATM switch 100. The switch 100 includes several input ports 110, several output ports 120, optical-to-digital (O/D) converters 130, digital-to-optical (D/O) converters 140, switching fabric 150, and controller 160. The input ports 110 receive data packets, including one or more cells, from a source on a corresponding set of high-speed optical input channels 115. The output ports 120 output the received cells to a destination on a corresponding set of high-speed optical output channels 125.
The OLD converters 130 connect to the input ports 110 to convert the received cells from optical signals to digital signals. The D/O converters 140 connect to the output ports 120 to convert the cells from digital signals back into optical signals for transmission by the output ports 120 on the output channels 125. The switching fabric 150 connects between the O/D and D/O converters 130 and 140. The switching fabric 150 transmits the received cells from an input port 110 to an appropriate output port 120 in response to a control signal from the controller 160. The controller 160 is a programmable device that controls the routing of the cells through the switch 100.
Cells arrive at the input ports 110 during a period called a time slot. In an ATM environment, the cells include a 5-octet header and a 48-octet information field. When a cell arrives at an input port 110, the controller 160 decodes the cell""s header to determine the proper output port 120 for the cell. The controller 160 then configures the switching fabric 150 to transmit the cell to this output port 120. When such a cell arrives at a single input port 110 destined for a single output port 120, the cell is called a xe2x80x9cunicastxe2x80x9d or xe2x80x9cpoint-to-pointxe2x80x9d cell. A xe2x80x9cmulticastxe2x80x9d cell, on the other hand, arrives at a single input port 110 destined for several of the output ports 120. In contrast, a xe2x80x9cbroadcastxe2x80x9d cell arrives at a single input port 110 destined for all of the output ports 120.
When several cells arrive at different input ports 110 destined for the same output port 120, conflicts or contentions result. Cell contention introduces throughput limitations, slowing the operation of the switch 100.
In addition, ATM protocol mandates that a switch 100 transmit cells from its output ports 120 in the same order that they arrived at its input ports 110. This makes the switch 100 effectively transparent to the communication medium by assuring that packets of arriving cells are not reordered when they leave the switch 100. With cells arriving on several different input ports 110 during each time slot, often contending for the same output ports 120, maintaining cell sequence and high throughput rates becomes difficult.
To address these deficiencies, conventional ATM switch architectures employ output-buffering, input-buffering, or shared memory techniques to facilitate data flow and maintain cell sequence between the input ports and the output ports. FIG. 2 is a block diagram of a conventional switch 200 employing the output-buffering technique. The switch 200 includes several input ports 210, several output ports 220, several output buffers 230, and a controller 240.
Each of the input ports 210 connects to all of the output buffers 230. The output ports 220, however, connect to only a single dedicated buffer 230. As a result, the buffers 230 contain multiple inputs and a single output. The controller 240 is a content addressable memory (CAM) controller that controls the operation of the buffers 230.
When a cell arrives at one of the input ports 210, the controller 240 decodes the cell""s header and instructs a particular one of the output buffers 230, corresponding to the designated output port 220, to store the cell. When the arriving cell is a multicast or broadcast cell, however, the controller 240 instructs several or all of the corresponding buffers 230 to store the cell during the time slot. If, for example, N cells destined for the same output port 220 arrive at different or all of the input ports 210, the controller 240 instructs the corresponding buffer 230 to store the N cells during a single time slot. To accomplish this, the switch 200 slows down its throughput rate N times. As a result, the per-port rate of output-buffered ATM switches, such as switch 200, becomes limited by the number of input ports 210.
Another conventional architecture is the input-buffering architecture. FIG. 3 is a block diagram of a conventional switch 300 employing the input-buffering technique. The switch 300 includes several input ports 310, several output ports 320, several-input buffers 330, a circuit switch matrix 340, and a controller 350.
Each of the input ports 310 connects to a dedicated one of the input buffers 330. The output ports 320, however, connect to all of the buffers 330 via the circuit switch matrix 340. The switch matrix 340 connects the input buffers 330 to the output ports 320 based on control signals from the controller 350. The controller 350 is a CAM controller that controls both the buffers 330 and the circuit switch matrix 340.
When a cell arrives on an input port 310, the input port 310 writes the cell directly into its dedicated input buffer 330. The controller 350 decodes the cell""s header and controls the switch matrix 340 to route the cell to the correct output port 320.
As with output-buffered architectures (e.g., FIG. 2), input-buffered ATM configurations suffer from reduced throughput. For example, assume that a first cell arrives at a first input buffer 330 for multicasting to two output ports 320. Assume also that second and third cells stored in other buffers 330 contend for the same two output ports 320. In this case, the first buffer 330 stores the first cell until the two output ports 320 become available. Because each buffer 330 can only transmit a single cell during any given time slot, the first buffer 330 cannot transmit the cells to both output ports 320 during the same time slot. Thus, the throughput becomes limited by the number of output ports 320.
Another conventional architecture is the shared-memory ATM architecture. FIG. 4 is a block diagram of a conventional switch 400 employing the shared memory technique. The switch 400 includes several input ports 410, several output ports 420, a shared buffer 430, and a controller 440.
Each of the input ports 410 and output ports 420 connect to the shared buffer 430. The shared buffer 430 is a common memory that stores and outputs cell data based on control signals from the controller 440. The buffer 430 efficiently stores the cells by permitting active input ports 410 to use the memory space of inactive input ports 410. The controller 440 is a CAM controller that controls the operation of the buffer 430.
Like the other conventional switches 100-300, the shared memory switch 400 also has its limitations. For example, during each time slot, the shared buffer 430 can only store N cells and output N cells, where N is the number of the input and output ports 410 and 420. This again results in reduced throughput by a factor of N.
The primary disadvantage of each of the above architectures is that the per-port bandwidth is limited by the number N of input and/or output ports. For example, assuming that a buffer can store a cell every 20 ns, then a transfer rate of 424/(20xc3x9710xe2x88x929)=21.2 Gbits/sec becomes possible, where 424 is the number of bits per cell written into the buffer in parallel. In the above prior art configurations, however, the number of input and/or output ports N limits the maximum possible transfer rate. Therefore, in each configuration the per-port input/output rates are defined by 21.2/N or S/N, where S is the input/output buffer speed. Thus, to obtain a per-port rate of 2.4 Gb/s, the maximum number of input and output ports becomes limited to eight.
To overcome the throughput and port limitations of the conventional switches, assignee of the present invention developed a merged buffer ATM (MBA) architecture with centralized control. The MBA architecture combines the advantages of the output buffering, input buffering, and shared memory architectures, while avoiding their disadvantages. The centralized control MBA architecture is described in U.S. Pat. No. 5,862,128, issued Jan. 19, 1998, which is incorporated by reference.
FIG. 5 is a block diagram of a centralized control MBA system 500. The system 500 includes several input ports 510, several output ports 520, several merged buffers 530, a circuit switch matrix 540, and a controller 550. Each of the input ports 510 receives cells of a data packet from a source over data channels. The input ports 510 connect to the merged buffers 530 via the circuit switch matrix 540 and conventional tristate devices 565. The switch matrix 540 transmits cells received at the input ports 510 to their proper buffers 530.
The merged buffers 530 include conventional memory devices for temporarily storing cells received at the input ports 510. Each of the merged buffers 530 connects to a corresponding one of the output ports 520. The buffers 530 also connect to the switch matrix 540 via feedback paths 560. The feedback path 560 includes conventional tristate devices 565.
The controller 550 controls the operation of the switch matrix 540 and the buffers 530. The controller 550 is a CAM controller that includes a header processor 555 to decode the cell headers and configure the switch matrix 540. The header processor 555 generates an internal routing header for the cells received at the input ports 510. The routing header includes information, such as the cell""s priority, the output port destination, and a sequence number defining the order in which the cell was received by the input port 510 with respect to other cells belonging to the same data packet.
The controller 550 stores a table of cell pointers that identify the locations in the buffers 530 at which the cells are stored. Using the cell pointer list, the controller 550 tracks the location of the cells as they move within the system 500.
The system 500 divides the cell processing time slot into two slots, time slot TSA and time slot TSB. During time slot TSA, the system 500 performs input and output functions (i.e., storing cells received at its input ports 510 and transmitting stored cells from its output ports 520). During time slot TSB, the system 500 processes cells stored within the merged buffers 530.
The system 500 processes cells as follows. During time slot TSA, the input ports 510 receive cells from the data channels. The controller 550 reads the cells"" headers to determine the destination output ports 520 for the cells. The controller 550 generates internal routing headers for the cells. The routing headers include, for example, the cell""s priority, the identity of the destination output port 520, and the cell""s sequence number.
Based on the destination output ports 520 for the cells, the controller 550 determines whether any output port conflict exists. An output port conflict exists when two or more cells contend for the same output port 520. The controller 550 resolves any conflicts using a conventional arbitration algorithm (e.g., based on xe2x80x9cfirst come,xe2x80x9d which resolves the conflict based on the first cell to arrive at an input port) to determine a xe2x80x9cwinnerxe2x80x9d cell and one or more xe2x80x9closerxe2x80x9d cells.
The controller 550 then configures the switch matrix 540 to route the winner cell and any non-conflicting cells to the destination buffers 530 corresponding to their destination output ports 520. The controller 550 configures the switch matrix 540 to route the loser cells to non-destination buffers 530. The xe2x80x9cdestinationxe2x80x9d and xe2x80x9cnon-destinationxe2x80x9d buffers are physically one buffer that is logically partitioned. The non-destination buffers 530 refer to any of the buffers other than the destination buffer 530. The controller 550 may determine which buffers to use as the non-destination buffers 530 in a number ways, including selecting a buffer randomly or sequentially.
The switch matrix 540 routes the cells to the destination buffers 530. When the buffers 530 store the cells, the controller 550 updates its table to record the location of the cells within the buffers 530.
While the above processing occurs, the controller 550 identifies the next cell in each buffer 530 to be sent to the corresponding output ports 520 based on information stored in its table. The controller 550 then instructs the buffers 530 to send the identified cells to the output ports 520 for transmission to their destinations.
During time slot TSB, the controller 550 determines the identity of the cells that have been xe2x80x9cmisroutedxe2x80x9d (i.e., routed to non-destination buffers 530). The controller 550 instructs the non-destination buffers 530 to output the identified cells to the feedback path 560. The tristates 565 enable the feedback path 560 to transmit the identified cells to the switch matrix 540.
Once again, the controller 550 determines whether any conflict exists among the misrouted cells. The controller 550 then determines the winner and loser cells and configures the switch matrix 540 to transmit the cells to the appropriate buffers 530. The above processing repeats for subsequent time slots until all of the originally received cells reach their destination buffers 530.
The centralized control MBA system 500 alleviates the throughput bottleneck that results when the number of ports increases in the conventional systems described above. A limitation still exists, however, because the controller 550 must service each of the ports for input and output cell processing during each time slot. Thus, when the number of ports increases, the time that the controller 550 can spend servicing a port during a time slot decreases.
If the system speed is 2.4 Gb/s and the time slot period equals 170 ns, the controller 550 must service all N ports during this 170 ns time slot. For a sixteen port system, for example, the controller 550 has approximately 10 ns to service each port. This 10 ns further reduces as the number of ports increases or as the port speed increases.
Therefore, a need exists to overcome the throughput and port limitations of the conventional switches described above.
Systems and methods consistent with the present invention address this need by providing a merged buffer architecture that eliminates the throughput and port limitations of the conventional architectures. The merged buffer architecture combines the advantages of the output buffering, the input buffering, and the shared memory architectures without their incorporating their disadvantages.
In accordance with the purpose of the invention as embodied and broadly described herein, a system consistent with the present invention includes input ports, output ports, and merged buffers corresponding to the output ports. Each of the input ports receives cells of a data packet from a source. The output ports output the cells in an order in which they were received by the input ports. The merged buffers temporarily store the cells received by the input ports. Each of the merged buffers includes an output buffer, and input buffer, and a controller. The output buffer stores cells for transmission by a corresponding one of the output ports. The input buffer temporarily stores cells for rerouting to at least one different one of the output ports. The controller reroutes the cells stored in the input buffer to output buffers corresponding to the different output ports.
In accordance with another implementation consistent with the present invention, a routing vector data structure guides a cell through a switch from its input port to its output port. The routing vector data structure includes an input port number, a sequence number, an output port number, and a misrouted cell sequence number. The input port number identifies an input port that received the cell. The sequence number identifies a position of the cell within a data packet. The output port number identifies an output port from which the cell is to be transmitted. The misrouted cell sequence number identifies the sequence of a cell routed to a buffer of an output port other than the output port identified by the output port number.